You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].
You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.
Return arr after applying all the updates.
Example 1:
Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]] Output: [-2,0,3,5,3]
Example 2:
Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]] Output: [0,-4,2,2,2,4,4,-4,-4,-4]
Constraints:
1 <= length <= 1050 <= updates.length <= 1040 <= startIdxi <= endIdxi < length-1000 <= inci <= 1000
Average Rating: 4.60 (25 votes)
Solution
Approach 1: Naïve Approach
Algorithm
The algorithm is trivial. For each update query, we iterate over the required update range and update each element individually.
Each query of updates is a tuple of 3 integers: start,end (the start and end indexes for the update range) and val (the amount by which each array element in this range must be incremented).
Complexity Analysis
-
Time complexity : O(n⋅k) (worst case) where k is the number of update queries and n is the length of the array. Each of the k update operations take up O(n) time (worst case, when all updates are over the entire range).
-
Space complexity : O(1). No extra space required.
Approach 2: Range Caching
Intuition
-
There is only one read query on the entire range, and it occurs at the end of all update queries. Additionally, the order of processing update queries is irrelevant.
-
Cumulative sums or
partial_sumoperations apply the effects of past elements to the future elements in the sequence.
Algorithm
The algorithm makes use of the above intuition to simply store changes at the borders of the update ranges (instead of processing the entire range). Finally a single post processing operation is carried out over the entire output array.
The two steps that are required are as follows:
-
For each update query (start,end,val) on the array arr, we need to do only two operations:
- Update start boundary of the range:
arrstart=arrstart+val
- Update just beyond the end boundary of the range:
arrend+1=arrend+1−val
-
Final Transformation. The cumulative sum of the entire array is taken (
0- based indexing)arri=arri+arri−1∀i∈[1,n)
Formal Explanation
For each update query (start,end,val) on the array arr, the goal is to achieve the result:
arri=arri+val∀i∈[start,end]
Applying the final transformation, ensures two things:
- It carries over the +val increment over to every element arri∀i≥start.
- It carries over the −val increment (equivalently, a +val decrement) over to every element arrj∀j>end.
The net result is that:
arriarrj=arri+val=arrj+val−val=arrj∀i∈[start,end]∀i∈(end,length)
which meets our end goal. It is easy to see that the updates over a range did not carry over beyond it due to the compensating effect of the −val increment over the +val increment.
It is good to note that this works for multiple update queries because the particular binary operations here (namely addition and subtraction):
-
are closed over the entire domain of
Integers. (A counter example is division which is not closed over allIntegers). -
are complementary operations. (As a counter example multiplication and division are not always complimentary due to possible loss of precision when dividing
Integers).
Complexity Analysis
-
Time complexity : O(n+k). Each of the k update operations is done in constant O(1) time. The final cumulative sum transformation takes O(n) time always.
-
Space complexity : O(1). No extra space required.
Further Thoughts
An extension of this problem is to apply such updates on an array where all elements are not the same.
In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of O(n).
@StefanPochmann suggested another method (see comment section) which does not require extra space, but requires an extra linear pass over the entire array. The idea is to apply reverse partial_sum operation on the array (for example, array [2,3,10,5] transforms to [2,1,7,−5]) as an initialization step and then proceed with the second method as usual.
Another general, more complex version of this problem comprises of multiple read and update queries over ranges. Such problems can be solved quite efficiently with Segment Trees by applying a popular trick called Lazy Propogation.
Analysis written by @babhishek21.
July 18, 2016 6:38 PM
An extension of this problem is to apply such updates on an array where all elements are not the same. In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of O(n).
Why? Can't you just apply "reverse partial_sum" to initialize? For example if given the array [2, 3, 10, 5], just change it to [2, 1, 7, -5] first.
March 27, 2021 6:08 AM
How does one come up with the intuition to be able to come up with this on the spot?
The "net result" equation in Formal Explanation section doesn't display correctly
So good. So neat. Hints are pretty useful. I am not saying because this I got the elegant solution.
March 6, 2019 7:25 PM
Hi,
Can you please provide more explanation on the reverse_partial_sum method?
Yes, it works, and that is a brilliant thought! Thanks @StefanPochmann
Last Edit: May 14, 2021 11:58 AM
How do you do partial_sum in java? is there any lib func?
or just
for (int i = 1; i < length; ++i) {
res[i] += res[i - 1];
}
amazes me that people can come up with solutions like this!
March 27, 2020 12:54 PM
Beautiful solution!
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: vector<int> getModifiedArray(int length, vector<vector<int>>& updates) { }};